package leetcode_滑动窗口;

import java.util.TreeSet;

/**
 * @author yzh
 * @version 1.0
 * @date 2022/4/24 22:41
 * 存在重复元素 III
 * 算法：滑动窗口
 * 维护一个大小为 k 的窗口
 */
public class _220 {

    public boolean containsNearbyAlmostDuplicate(int[] nums, int k, int t) {
        int n = nums.length;
        TreeSet<Long> ts = new TreeSet<>();
        for (int i = 0; i < n; i++) {
            Long u = nums[i] * 1L;
            Long l = ts.floor(u);
            Long r = ts.ceiling(u);
            if (l != null && u - l <= t) return true;
            if (r != null && r - u <= t) return true;
            // 如果有相同的元素，那么会直接返回 true, 因此无需注意相同的元素
            // 必须 ts.add(u), [1, 2] 0 1, 可能会出现滑动窗口大小为 0 的例子
            ts.add(u);
            if (i >= k) ts.remove(nums[i - k] * 1L);
        }
        return false;
    }

}
